/* 1774. 最接近目标价格的甜点成本 */
/**
 * @param {number[]} baseCosts
 * @param {number[]} toppingCosts
 * @param {number} target
 * @return {number}
 */
// 回溯
var closestCost = function (baseCosts, toppingCosts, target) {
	let res = Math.min(...baseCosts)
	const dfs = (toppingCosts, p, curCost, target) => {
		// res < curCost
		if (Math.abs(res - target) < curCost - target) {
			return
		}
		if (Math.abs(res - target) >= Math.abs(curCost - target)) {
			if (Math.abs(res - target) > Math.abs(curCost - target)) {
				res = curCost
			} else {
				res = Math.min(res, curCost)
			}
		}
		if (p === toppingCosts.length) return
		// 添加一种或多种配料[同一种配料最多2份]
		dfs(toppingCosts, p + 1, curCost + toppingCosts[p] * 2, target)
		dfs(toppingCosts, p + 1, curCost + toppingCosts[p], target)
		dfs(toppingCosts, p + 1, curCost, target)
	}
	for (const b of baseCosts) {
		dfs(toppingCosts, 0, b, target)
	}
	return res
}
closestCost([1, 7], [3, 4], 10)
